Both Golay coding and the utilization in connection therewith of the Kasami algorithm for error trapping purposes are well known and understood by those skilled in the art. The Golay code is a specific code defined as an (n, k, t) or (23, 12, 3) polynomial code in which each codeword is n=23 bits long, contains k=12 data or information bits, and corrects up to t=3 errors. The codeword also includes (n-k)=11 redundant check bits. The Golay code is a perfect code in that each codeword differs from every other codeword by exactly seven bits, which difference represents the so-called Hamming distance. The perfect nature of the Golay code is advantageous in that more errors can be corrected in a Golay codeword than in any other polynomial code of the same bit length. As in the case for all polynomial codes, encoding is relatively easy and straightforward. In general, a polynomial code is defined in terms of a generator polynomial g(x) which, for the Golay code, can be expressed in one well known form by g(x)=x.sup.11 +x.sup.10 +x.sup. 6 +x.sup.5 +x.sup.4 +x.sup.2 +1. The (n-k)=11 redundancy check bits that must be appended to the n=12 information or data bits are determined by multiplying the data bits by x.sup.(n-k) and dividing the result by the generator polynomial g(x).
A properly generated and transmitted Golay codeword, if received in an error-free fashion, is an exact multiple of the generator polynomial g(x), that is, the codeword when divided by g(x) yields a remainder, or so-called "syndrome" word, of zero. If errors are introduced into a Golay codeword during transmission, the resulting syndrome word is other than zero, and error correction is achieved by adding a polynomial number, in a modulo-2 operation, to the codeword to make the codeword exactly divisible by g(x). The Golay code is a cyclic code in that any Golay codeword can be rotated or shifted left or right any number of bits and the result will be another valid Golay codeword exactly divisible by g(x). The Golay codeword is referred to as a halfrate Golay code because nearly twice as many bits are now required to transmit the same information.
Errors in a Golay codeword as discussed above can be "trapped" by the aforementioned Kasami algorithm. The Kasami error trapping algorithm tests a Golay code-word to detect one of three possible different error patterns and, depending on which error pattern is detected, alters the codeword to correct for the presence of the errors. Up to three errors, that is, three incorrect bits in a Golay codeword, can be corrected by the Kasami error trapping algorithm. The Kasami algorithm is described in detail in an article entitled "A Decoding Procedure for Multiple-Error-Correcting Cyclic Codes", by Tadao Kasami, IEEE Transactions on Information Theory, April, 1964, pp. 134-138.
Heretofore, it has been proposed to implement the Kasami error trapping algorithm as described briefly hereinabove by the use of a look-up table, for example, in PROM (programmable read only memory), which is addressed by the syndrome word and the result employed to correct a Golay codeword in software. Such a lookup table, however, requires 2047 words of 12 bits each, or 24 kilobits, and implementation of the table alone requires twelve 512.times.4 bit PROMS. This solution therefore, although having the advantage of very fast correction speed, is costly from a hardware standpoint.